package com.leetcode.algorithm.y22.m08.w1;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 572. 另一棵树的子树
 * 
 * https://leetcode.cn/problems/subtree-of-another-tree/
 * 
 * @author jie.deng
 *
 */
class Question0572Solution01 {

	public boolean isSubtree(TreeNode root, TreeNode subRoot) {
		return isSame(root, subRoot)
				|| (root != null && (isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)));
	}

	private boolean isSame(TreeNode node1, TreeNode node2) {
		if (node1 == null || node2 == null) {
			return node1 == node2;
		}
		return node1.val == node2.val && isSame(node1.left, node2.left) && isSame(node1.right, node2.right);
	}

}